package leetcode.editor.cn;

import java.util.*;
import leetcode.editor.common.*;

public class MaximumSubarray {

    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        public int maxSubArray(int[] nums) {
            // 使用滑动窗口
            int maxSum = Integer.MIN_VALUE;
            int windowSum = 0;
            int left = 0;
            int right = 0;
            // 还没到头，继续向右滑动
            while (right<nums.length){

                windowSum+=nums[right];
                right++;



                maxSum = Math.max(maxSum,windowSum);


                // 如果 窗口和为负数，则需要移动左边界，缩小窗口===》 为什么 要左移
                // 想要和尽量大， 应该尽可能向正数靠拢，和为负数  说明  有负数了，要赶紧跑
                while (windowSum<0){
                    windowSum-=nums[left];
                    left++;
                }
            }
            return maxSum;
        }
    }
    //leetcode submit region end(Prohibit modification and deletion)

    
    public static void main(String[] args) {
        Solution solution = new MaximumSubarray().new Solution();
        // put your test code here
        
    }
}
